package LimitedTimeGame.Day_0205;

/**
 * @author zxc
 * @date 2023/02/05 10:25
 **/

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目 ：穿过迷宫的最少移动次数
 * 题目详述 ：
 * 在一个n*n的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。
 * 蛇会从左上角（(0, 0)和(0, 1)）开始移动。
 * 我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2)和(n-1, n-1)）。
 * 每次移动，蛇可以这样走：
 * 如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
 * 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
 * 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
 * 如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。
 * 返回蛇抵达目的地所需的最少移动次数。
 * 如果无法到达目的地，请返回-1。
 *
 * 提示：
 * 2 <= n <= 100
 * 0 <= grid[i][j] <= 1
 * 蛇保证从空单元格开始出发。
 *
 */
public class MinimumMoves02 {
    /**
     * 思路 ：
     * 假设f(x,y,status)代表了 贪吃蛇尾节点(x,y) && 贪吃蛇状态status（水平/垂直状态）所唯一确定的贪吃蛇位置，从(0,0,0)开始到达该位置所需要的最少移动次数;
     * ===>
     * 1.status == 0情况下，
     * （1）贪吃蛇右移一格;
     * （2）贪吃蛇下移一格;
     * （3）贪吃蛇顺时针旋转;
     *
     * 2.status == 1情况下，
     * （1）贪吃蛇右移一格;
     * （2）贪吃蛇下移一格;
     * （3）贪吃蛇逆时针旋转;
     *
     * 3.要谈论 status == 0/1条件下的所有可能情况，同时需要满足 dp[i][j][status]是首次被初始化 && 首次被赋值;
     * ===》
     * （1）由于采用的广度优先遍历，即，dp数组中元素首次所赋予的值必然是 从 起点 到达 当前所指向贪吃蛇状态 的最少移动次数;
     * （2）由于存在 顺时针/逆时针旋转对于贪吃蛇状态的的改变 && 当前贪吃蛇有三种移动方式 ：右移，下移，顺时针/逆时针旋转;
     *  ===> 即，若是不去判断当前遍历的dp数组元素值是否为初次赋值，则会出现 异常;
     *
     * @param grid
     * @return
     */
    public int minimumMoves(int[][] grid) {
        int len = grid.length;
        int[][][] dp = new int[len][len][2];
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < len ; j++){
                Arrays.fill(dp[i][j] , -1);
            }
        }
        dp[0][0][0] = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0 , 0 ,0});
        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            int status = poll[2];
            if(status == 0){
                if(y + 2 < len && grid[x][y + 2] == 0 && dp[x][y + 1][status] == -1){
                    dp[x][y + 1][status] = dp[x][y][status] + 1;
                    queue.offer(new int[]{x , y + 1 , status});
                }
                if(x + 1 < len && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0 && dp[x + 1][y][status] == -1){
                    dp[x + 1][y][status] = dp[x][y][status] + 1;
                    queue.offer(new int[]{x + 1 , y , status});
                }
                if(x + 1 < len && y + 1 < len && dp[x][y][1 - status] == -1 && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0){
                    dp[x][y][1 - status] = dp[x][y][status] + 1;
                    queue.offer(new int[]{x , y , 1 - status});
                }
            }
            else {
                if(y + 1 < len && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0 && dp[x][y + 1][status] == -1){
                    dp[x][y + 1][status] = dp[x][y][status] + 1;
                    queue.offer(new int[]{x , y + 1 , status});
                }
                if(x + 2 < len && grid[x + 2][y] == 0 && dp[x + 1][y][status] == -1){
                    dp[x + 1][y][status] = dp[x][y][status] + 1;
                    queue.offer(new int[]{x + 1 , y , status});
                }
                if(x + 1 < len && y + 1 < len && dp[x][y][1 - status] == -1 && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0){
                    dp[x][y][1 - status] = dp[x][y][status] + 1;
                    queue.offer(new int[]{x , y , 1 - status});
                }
            }
        }
        return dp[len - 1][len - 2][0];
    }
    /**
     * 分析 ：
     * 1.贪吃蛇当前位置 ：(x,y,status)
     *  ===> (x,y)，为贪吃蛇尾部节点位置;status，为贪吃蛇当前状态（水平/垂直状态）;
     * 2.要到达当前贪吃蛇位置，有三种可能性：
     * （1）(x,y-1,status)向右移动到达(x,y,status);
     * （2）(x-1,y,status)向下移动到达(x,y,status);
     * （3）(x,y,1-status)逆时针/顺时针进行旋转到达(x,y,status);
     *  ===> 即，第三种情况就是 贪吃蛇尾节点是相同的 && （水平状态 -> 垂直状态 || 垂直状态 -> 水平状态）;
     */
}
